#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int len = nums.size();
        if (len <= 2) {
            return 0;
        }
        sort(nums.begin(), nums.end());
        int outcome = 0;

        // 固定最大的边c（从后往前遍历）
        for (int c = len - 1; c >= 2; c--) {
            int left = 0, right = c - 1;
            while (left < right) {
                // 如果两边之和大于第三边，满足三角形条件
                if (nums[left] + nums[right] > nums[c]) {
                    // 所有left到right-1的数与right、c都能组成三角形
                    outcome += right - left;
                    right--;
                }
                else {
                    // 两边之和太小，需要增大较小的边
                    left++;
                }
            }
        }
        return outcome;
    }
};

int main() {
    Solution solution;

    // 测试用例1: 正常情况
    vector<int> nums1 = { 2, 2, 3, 4 };
    cout << "测试用例1 [2,2,3,4]: " << solution.triangleNumber(nums1) << " (期望: 3)" << endl;

    // 测试用例2: 包含0的情况
    vector<int> nums2 = { 0, 1, 1, 1 };
    cout << "测试用例2 [0,1,1,1]: " << solution.triangleNumber(nums2) << " (期望: 1)" << endl;

    // 测试用例3: 所有元素相同
    vector<int> nums3 = { 4, 4, 4, 4 };
    cout << "测试用例3 [4,4,4,4]: " << solution.triangleNumber(nums3) << " (期望: 4)" << endl;

    // 测试用例4: 无法构成三角形
    vector<int> nums4 = { 1, 2, 3, 4, 5 };
    cout << "测试用例4 [1,2,3,4,5]: " << solution.triangleNumber(nums4) << " (期望: 3)" << endl;

    // 测试用例5: 空数组
    vector<int> nums5 = {};
    cout << "测试用例5 []: " << solution.triangleNumber(nums5) << " (期望: 0)" << endl;

    // 测试用例6: 元素不足3个
    vector<int> nums6 = { 1, 2 };
    cout << "测试用例6 [1,2]: " << solution.triangleNumber(nums6) << " (期望: 0)" << endl;

    // 测试用例7: 较大数组
    vector<int> nums7 = { 3, 4, 5, 6, 7, 8 };
    cout << "测试用例7 [3,4,5,6,7,8]: " << solution.triangleNumber(nums7) << " (期望: 20)" << endl;

    // 测试用例8: 包含重复元素
    vector<int> nums8 = { 2, 2, 3, 3, 4, 4 };
    cout << "测试用例8 [2,2,3,3,4,4]: " << solution.triangleNumber(nums8) << " (期望: 16)" << endl;

    return 0;
}